package leetcode_core.leetcode_1;

import org.junit.Test;

public class MaxCoinsByDp {

    public int maxCoins(int[] nums) {
        //1.扩展数组
        int n = nums.length;
        int[] points = new int[n+2];
        points[0]=points[n+1]=1;
        for(int i = 1;i<points.length-1;i++){
            points[i] = nums[i-1];
        }
        //2.定义dp数组,注意(i,j)是开区间,代表这个区间内的所能得到的最大得分,最小下标0,最大下标n+1
        int[][] dp = new int[n+2][n+2];
        //3.写出base-case,注意到dp的区间是(i,j),所以当j<=i+1的时候就压根就没有这个区间,那么也就压根没有最大值可以选了
        //想一下(i,i+1)这个区间有值吗?至少得2吧
        for(int i =0;i<=n+1; i++){
            for(int j = 0;i!=n+1&&j<=i+1;j++){
                dp[i][j] = 0;
            }
        }
        //4.状态转移推算,从下到上,从中间对角线到右上角,保证每一个值的下边和左边都被计算过了,因为n+1的那一行已经被计算过了(base-case),因此直接从n开始算
        for(int i = n;i>=0;i--){
            for(int j = i+1 ; j<n+2; j++){
                //做选择,从(i,j)里面选一个k出来
                for(int k = i+1;k<j;k++){
                    dp[i][j] = Math.max(dp[i][j],
                            dp[i][k]+dp[k][j]+(points[k]*points[i]*points[j]));
                }
            }
        }
        return dp[0][n+1];
    }

    @Test
    public void testcase1(){
        int[] case1 = new int[]{3,1,5,8};
        System.out.println(maxCoins(case1));
    }

    @Test
    public void testcase2(){
        int[] case2 = new int[]{1,5};
        System.out.println(maxCoins(case2));
    }
}
